\documentclass{beamer}

\usepackage{amsthm}
\usepackage{beamerthemesplit}
\newcommand{\maxflow}{\text{MAXFLOW}}
\newcommand{\mincut}{\text{MINCUT}}
\newtheorem{thm}{Theorem}
\newtheorem{defn}{Definition}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}

\title{Multicommodity Flow}
\author{Sarah Fletcher and Michael Xu}
\date{November 3rd, 2009}
\begin{document}
\AtBeginSection[]
{
  \begin{frame}
    \frametitle{Outline}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}
\frame{\titlepage}

%% introduction section
\section{Introduction}

%% new section
\section{Single Commodity Flow}
\subsection{Single Commodity Flow Networks}
\begin{frame}
  
\begin{columns}
\column{.5\textwidth}
\begin{block}{Single Commodity Flow}
A directed flow network  is a graph $G = (V, E)$ where:
\begin{itemize}
\item each edge has a capacity $c_e$
\item a source node $s \in V$
\item a sink node $t \in V$.
\end{itemize}
\end{block}
\column{.5\textwidth}
\begin{block}{}
\includegraphics[height=1.8in]{hello.pdf}
\end{block}
\end{columns}
\end{frame}
\subsection{Ford-Fulkerson Method}
\begin{frame}
  \frametitle{ \subsecname}
  
  \begin{itemize}
  \item Find an Initial Flow $f$
    \item Repeat until no augmenting flows
\begin{itemize}
  \item Build a Residual Graph
  \item Find Augmenting Flow
  \item Add to flow $f$
  \end{itemize}
    \end{itemize}
\end{frame}

\subsection{Initial Flow}
\begin{frame}
  
  \frametitle{\secname}
  \centering
\includegraphics[height=2.5in]{initial.pdf}
\end{frame}


\subsection{Residual Graphs}
\begin{frame}

  \frametitle{\secname}
  \begin{itemize}
  \item In the direction of the original directed edge in $G$, $R$ has an edge of capacity $c_e - k(f)$. 
  \item In the opposite direction of the original directed edge, $R$ has a directed edge of capacity $k(f)$.
  \end{itemize}
  \begin{figure}
  \centering
  \includegraphics[height=2in]{residual.pdf}
  \end{figure}
  \end{frame}
  
  \subsection{Iterative Augmentation}
  \begin{frame}
  \begin{itemize}
  \item $f$ is increased by integer amounts
  \item A max-flow $f_\text{max}$ is guaranteed
  \item When Ford-Fulkerson ends, no path from $s$ to $t$ on residual graph $R$ exists
  \item This is a cut $C$
  \end{itemize}
  \end{frame}

\subsection{Max-Flow is Min-Cut}
\begin{frame}
  \frametitle{\secname}
  
  \begin{itemize}
  \item $f_\text{max}$ is at most min-cut,
  \item min-cut must be at least $C$. 
  \end{itemize}
  Combining these, 
\[\text{min-cut}  \leq C = f_{\text{max}} \leq \text{min-cut}.\]
\[\text{max-flow} = \text{min-cut}.\]
\end{frame}

\section{MultiCommodity Flow}
\subsection{MultiCommodity Flow Networks}
\begin{frame}
  \begin{columns}
    \column{.5\textwidth}
    \begin{block}{MultiCommodity Flow}
      A \emph{multicommodity flow network} is a graph $G = (V, E)$ with 
      \begin{itemize}
      \item pairs of vertices $s_i,t_i\in V$, each representing a source and sink for a commodity $i$
      \item a demand $D_i$ for each commodity
      \item a capacity function $C$ on the edges of $G$ such that
        \[\sum_{\text{all }i}f_i(e)\leq c_e\]
      \end{itemize}
    \end{block}
    \column{.5\textwidth}
    \begin{block}{}
      \begin{figure}[]
        \includegraphics[height = 1.4in]{mflownetwork.png}
      \end{figure}
    \end{block}
  \end{columns}
\end{frame}
\begin{frame}
  \begin{block}{Uniform Multicommodity Flow Problems UMFP}
    \begin{itemize}
    \item there is a commodity that needs to be transferred between every pair of vertices
\item each commodity has demand $1$
\item concurrent max-flow - the largest $f\in[0,1]$ so that we can find a flow with $f$ between each pair of vertices
\item min-cut - the smallest capacity/demand ration over all cuts in the graph
 \[min_{U\subseteq V} \frac{\text{edges between } U\text{ and }\overline{U}}{|U||\overline{U}|}\]
\end{itemize}
\end{block}
\end{frame}
\subsection{Example: An $O(\log (n))$ gap} 
\begin{frame}
Let $c>0$ and $G=(VE)$ be a $3$-regular graph with the property that for any subset $U$ of $V$
\[\text{number of edges between } U\text{ and }\overline{U}\geq c\min\{|U|,|\overline{U}|\}.\]
  \begin{itemize}
  \item min-cut $\displaystyle{ M = \frac{c}{n-1}}$
  \item For a concurrent flow rate of $f$, we need total capacity at least 
\[\frac{1}{2}\binom{n}{2} f(\log(n)-2)\]
   \item $f\leq O\left(\frac{M}{\log(n)}\right)$
  \end{itemize}
\end{frame}
\subsection{Max-flow is $\Omega (\log(n))$ Min-cut}
\begin{frame}
 \begin{thm}[Leighton, Rao - 1999]
For any uniform multicommodity flow problem with $n$ vertices,
\[\Omega\left(\frac{\mincut}{\log(n)}\right)\leq  \maxflow \leq \mincut.\]
\end{thm}
\end{frame}


\begin{frame}
\begin{lem} For any graph $G=(V,E)$ with an arbitrary capacity function $c$, any $\Delta>0$ and any distance function with total weight $W$, it is possible to partition $G$ into components with radius at most $\Delta$ so that the capacity of the edges connecting nodes in different components is at most $4W \log n/\Delta$.  
\end{lem}

\pause
\begin{cor}\label{cor}
For any graph $G$ and any distance function with total weight $W$, we can either  find a component with radius at most $\frac{1}{2n^2}$ that contains at least $2/3$ of the vertices in $G$
or find a cut of  $G$ with ratio cost  $O(W \log n)$.
\end{cor}
\end{frame}

\begin{frame}
We can partition $G$ into components of radius at most $\Delta$ with at most $4W \log n/\Delta$ capacity between components. There is either a component with radius at most $\frac{1}{2n^2}$ that contains at least $2/3$ of the vertices in $G$ or a cut of  $G$ with ratio cost  $O(W \log n)$.

 \begin{lem}
For any graph $G$, if there is a distance function $d$ with total weight $W$ and a subset of vertices $T\subseteq V$ with $|T|\geq 2n/3$ and 
\[\sum_{u\in V-T}d(T,u) \geq \frac{1}{2n},\]
then we can find a cut with ratio cost  $O(W)$.
\end{lem}
\end{frame}

\begin{frame}
We can partition $G$ into components of radius at most $\Delta$ with at most $4W \log n/\Delta$ capacity between components. There is either a component $T$ with radius at most $\frac{1}{2n^2}$ that contains at least $2/3$ of the vertices in $G$ or a cut of  $G$ with ratio cost  $O(W \log n)$.  If we have $T$ and a distance function that satisfies
\[\sum_{u\in V-T}d(T,u) \geq \frac{1}{2n},\]
then we can find a cut with ratio cost  $O(W)$.
\begin{lem}
Given a graph $G$ and a distance function with total weight $W$ that satisfies $\sum_{u,v\in V} d(u,v) \geq 1$, we can find a cut with ratio cost $O(W \log n).$
\end{lem}
\end{frame}


\section{Applications}
\begin{frame}
\frametitle{Graph Partitioning}
\begin{itemize}
\item Sparsest cut
\item Balanced cuts and separators
\item Minimum cut linear arrangement
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{More Applications}
\begin{itemize}
\item Crossing number of a graph
\item VLSI layout
\item Uniprocessor Scheduling
\end{itemize}
\end{frame}

\end{document}
